//
//  FindLength.swift
//  LeetCodeSummary
//
//  Created by WangYonghe on 2020/7/2.
//  Copyright © 2020 WangYonghe. All rights reserved.
//  718. 最长重复子数组    tag:数组 哈希表 二分查找 动态规划

import UIKit

/*
 718. 最长重复子数组
 给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。

  

 示例：

 输入：
 A: [1,2,3,2,1]
 B: [3,2,1,4,7]
 输出：3
 解释：
 长度最长的公共子数组是 [3, 2, 1] 。
  

 提示：

 1 <= len(A), len(B) <= 1000
 0 <= A[i], B[i] < 100
 */

class FindLength: NSObject {
    
    //可以用滑窗的方法
    /*
     我们可以枚举 A 和 B 所有的对齐方式。对齐的方式有两类：第一类为 A 不变，B 的首元素与 A 中的某个元素对齐；第二类为 B 不变，A 的首元素与 B 中的某个元素对齐。对于每一种对齐方式，我们计算它们相对位置相同的重复子数组即可。
     详情如图
     https://assets.leetcode-cn.com/solution-static/718/718_fig1.gif
     */
    func findLength(_ A: [Int], _ B: [Int]) -> Int {
        
        var max1 = 0
        var max2 = 0
        //先固定A 让B往后错位  每次比较求出最长子数组
        for index in 0 ..< A.count{
            let result = self.maxSubArrCount(A, B, 0, index)
            max1 = max(result, max1)
        }
        //先固定B 让A往后错位  每次比较求出最长子数组
        for index in 0 ..< B.count{
            let result = self.maxSubArrCount(A, B, index, 0)
            max2 = max(result, max2)
        }
        
        return max(max1, max2)
    }
    
    func maxSubArrCount(_ arr1:[Int], _ arr2:[Int], _ offset1:Int, _ offset2:Int)->Int{
        let c1 = arr1.count
        let c2 = arr2.count
        
        var loopIndex = 0
        
        if offset1 == offset2{
            loopIndex = min(c1, c2)
        }else{
            if offset1 < offset2 {
                //数组A不动  数组B往后移动
                if offset2 + c2 <= c1 {
                    loopIndex = c2
                }else{
                    /*
                     eg:   1 2 3 4 5
                               4 5 2 6
                     c1 = 5, c2 = 4, offset = 2
                     以下公式可以算出本循环次数为3
                     */
                    loopIndex = c2 - (offset2 + c2 - c1)
                }
            }else{
                //数组A往后移动  数组B不动
                if offset1 + c1 <= c2 {
                    loopIndex = c2
                }else{
                    loopIndex = c1 - (offset1 + c1 - c2)
                }
            }
        }
        
        var maxLenth = 0
        var ret = 0
        for index in 0 ..< loopIndex{
            //比较的时候 A[i+B的偏移量] 和 B[i]进行比较  反之亦然
            if arr1[index + offset2] == arr2[index + offset1] {
                maxLenth = maxLenth + 1
            }else{
                maxLenth = 0
            }
            ret = max(ret, maxLenth)
        }
        //print("本次offset1=\(offset1),offet2=\(offset2),最长相同子串长度为\(ret)")
        return ret
    }
    
    
    
    
    /*
     更加强大的动态规划思路
     
     
     eg: A = [1,2,3,2,1]    B = [3,2,1,4,7]

     列表格
            1   2   3   2   1
     
        3           1
        
        2       1       1
     
        1   1               1
     
        4
        
        7
     
     如果某个位置上横竖两个数字相同 在表格里面用”1“来表示
     
     左上-右下（↖
                 ↘）方向能连起来的地方  就是两个数组的相同公共子串 求出最长线的长度即可
     
     
     */
    
}
